//! ## 二路梯形图(binary trapezoid), 功能类似于二叉树

//  use std::rc::Rc;
//
//  include!("macros.rs");
//  mod error;
//  use error::XErr;
//
//  pub trait Key: Eq + PartialEq + Ord + PartialOrd {}
//
//  pub struct Trapezoid<K: Key, V> {
//      root: Option<Rc<Node<K, V>>>,
//  }
//
//  pub struct Node<K: Key, V> {
//      key: K,
//      value: Rc<V>,
//
//      parent: Option<Rc<Node<K, V>>>,
//      left: Option<Rc<Node<K, V>>>,
//      right: Option<Rc<Node<K, V>>>,
//      cleft: Option<Rc<Node<K, V>>>,
//      cright: Option<Rc<Node<K, V>>>,
//  }
//
//  impl<K: Key, V> Trapezoid<K, V> {
//      pub fn set(&mut self, key: K, value: V) -> Result<Rc<Node<K, V>>, XErr<K, V>> {
//          let new = Rc::new(Node::new(key, value));
//          match self.get(&key) {
//              Ok(n) => Err(XErr::AlreadyExists(n)),
//              Err(XErr::NotExists(None)) => {
//                  self.root = Some(new);
//                  Ok(self.root.clone().unwrap())
//              }
//              Err(XErr::NotExists(Some(n))) => {
//                  let mut raw;
//                  //此时的n,必然位于最底一层
//                  //大于在右,小于在左,不可能等于
//                  if key > n.key {
//                      if let Some(tail) = Self::check_orphan_at_right(n) {
//                      } else {
//                      }
//                  } else {
//                  }
//              }
//              Err(e) => Err(e),
//          }
//      }
//
//      pub fn get_value(&self, key: &K) -> Option<Rc<V>> {
//          self.get(key).ok().map(|n| Rc::clone(&n.value))
//      }
//
//      fn get(&self, key: &K) -> Result<Rc<Node<K, V>>, XErr<K, V>> {
//          let mut cursor = if let Some(root) = self.root.as_ref() {
//              Rc::clone(root)
//          } else {
//              return Err(XErr::NotExists(None));
//          };
//
//          if *key == cursor.key {
//              return Ok(cursor);
//          }
//
//          'outer: loop {
//              if *key > cursor.key {
//                  while let Some(right) = cursor.right.as_ref() {
//                      if *key == right.key {
//                          return Ok(Rc::clone(right));
//                      } else if *key > right.key {
//                          cursor = Rc::clone(right);
//                          continue;
//                      } else if let Some(cleft) = right.cleft.as_ref() {
//                          cursor = Rc::clone(cleft);
//                          continue 'outer;
//                      }
//                  }
//                  if let Some(cright) = cursor.cright.as_ref() {
//                      cursor = Rc::clone(cright);
//                      continue 'outer;
//                  } else {
//                      return Err(XErr::NotExists(Some(cursor)));
//                  }
//              } else {
//                  while let Some(left) = cursor.left.as_ref() {
//                      if *key == left.key {
//                          return Ok(Rc::clone(left));
//                      } else if *key < left.key {
//                          cursor = Rc::clone(left);
//                          continue;
//                      } else if let Some(cright) = left.cright.as_ref() {
//                          cursor = Rc::clone(cright);
//                          continue 'outer;
//                      }
//                  }
//                  if let Some(cleft) = cursor.cleft.as_ref() {
//                      cursor = Rc::clone(cleft);
//                      continue 'outer;
//                  } else {
//                      return Err(XErr::NotExists(Some(cursor)));
//                  }
//              }
//          }
//      }
//  }
//
//  impl<K: Key, V> Node<K, V> {
//      fn new(k: K, v: V) -> Node<K, V> {
//          Node {
//              key: k,
//              value: Rc::new(v),
//              parent: None,
//              left: None,
//              right: None,
//              cleft: None,
//              cright: None,
//          }
//      }
//  }
